//给定一个三角形 triangle ，找出自顶向下的最小路径和。
//
// 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果
//正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
//
//
//
// 示例 1：
//
//
//输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
//输出：11
//解释：如下面简图所示：
//   2
//  3 4
// 6 5 7
//4 1 8 3
//自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
//
//
// 示例 2：
//
//
//输入：triangle = [[-10]]
//输出：-10
//
//
//
//
// 提示：
//
//
// 1 <= triangle.length <= 200
// triangle[0].length == 1
// triangle[i].length == triangle[i - 1].length + 1
// -10⁴ <= triangle[i][j] <= 10⁴
//
//
//
//
// 进阶：
//
//
// 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？
//
//
//
//
//
// 注意：本题与主站 120 题相同： https://leetcode-cn.com/problems/triangle/
//
// Related Topics 数组 动态规划 👍 37 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function minimumTotal(triangle: number[][]): number {

    /*
          1
        -5 -2
        3 6 1
      -1 2 4 -3
     */
    const m = triangle.length
    const dp: number[][] = new Array(m).fill(0)
    dp[0] = []
    dp[0][0] = triangle[0][0]
    //? 只存在根
    if (m === 1) return triangle[0][0]
    //? 记录最小
    let min = Infinity
    for (let i = 1; i < m; i ++) {
        //? 每层的长度不同 所以需要动态添加
        const n = triangle[i].length
        dp[i] = []
        //? 遍历该层的每个节点
        for (let j = 0; j < n; j ++) {
            //? 比较此节点能从哪个父来
            let d1 = dp[i - 1][j]
            let d2 = dp[i - 1][j - 1]
            //? 判断只有一个父的情况 这里必须指定undefined
            if (dp[i - 1][j] === undefined) {
                d1 = Infinity
            }
            if (dp[i - 1][j - 1] === undefined) {
                d2 = Infinity
            }
            //? 选更小的路径
            const f = Math.min(d1,d2)
            dp[i][j] = f + triangle[i][j]
            //? 到达最后一层 判断最小路径长度
            if (i === m - 1 && min > dp[i][j]) min = dp[i][j]
        }
    }
    return min

};
//leetcode submit region end(Prohibit modification and deletion)
